package 力扣_树算法.树与链表;


/**剑指 Offer 36. 二叉搜索树与双向链表
 *
 * @author zx
 * @create 2022-04-15 8:58
 */
public class Offer36 {
    /**
     * 非虚拟头节点版
     */
    Node prev = null;
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        //使双向链表变为循环双向链表
        inOrder(root);
        //当构建完双向链表,prev指向最后一个节点
        head.left = prev;
        prev.right = head;
        return head;
    }
    //传入root为根节点的二叉搜索树,将其构建为双向链表
    private void inOrder(Node root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        if(prev != null){
            prev.right = root;
        }else{
            head = root;//确定头节点
        }
        root.left = prev;
        prev = root;//这里用这个就是错的：prev = prev.right;
        inOrder(root.right);
    }


    /**
     * 虚拟头节点版
     */
    //Node prev = null;
    public Node treeToDoublyList2(Node root) {
        if(root == null){
            return null;
        }
        Node dummy = new Node(-1);
        prev = dummy;
        inOrder(root);
        prev.right = dummy.right;
        dummy.right.left = prev;
        return dummy.right;
    }
    //传入root为根节点的二叉搜索树,将其构建为双向链表
    private void inOrder2(Node root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        prev.right = root;
        root.left = prev;
        prev = root;//这里可用这个：prev = prev.right;(用统一的,好记)
        inOrder(root.right);
    }
}
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
